package com.yc.algorithm.leetcode;


import java.util.HashMap;

/**
 * 哈希表查找快，但数据是无固定顺序的
 * 链表是有顺序，插入和删除快，但查找慢
 * 所以需要新的数据结构为：哈希链表（LinkedHashMap）
 */
public class LRUCache {

    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecentlyKey(key, value);
        } else {
            // 判断容量
            if (cap == cache.size()) {
                // 淘汰最近未使用
                removeLeastRecently();
            }
            addRecentlyKey(key,value);
        }
    }

    // 使指定key为最近key
    public void makeRecently(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    // 删除keY
    public void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    // 添加最近使用
    public void addRecentlyKey(int key, int val){
        Node x = new Node(key, val);
        cache.addLast(x);
        map.put(key, x);
    }

    // 删除最近未使用的key
    public void removeLeastRecently(){
        Node first = cache.removeFirst();
        map.remove(first.key);
    }
}

// 定义一个hash链表
class DoubleList{

    // 链表的头尾结点
    private Node head, tail;

    // 链表的size
    private int size;

    // 初始化双向链表
    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 向链表的尾部添加结点x, 时间为 O(1)
    public void addLast(Node x){
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // 删除元素，不考虑null
    public void remove(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // 删除链表中第一个元素并返回
    public Node removeFirst(){
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        remove(first);
        return first;
    }

    // 返回链表长度
    public int size(){
        return size;
    }
}

// 定义哈希链表结点对象
class Node{
    public int key, val;
    public Node next, prev;
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}


